package com.gaogzhen.datastructure.stack;

import java.util.*;

public class ExpressionEval {

    public static Map<String, Integer> operators;
    // 存放转换后的后缀表达式
    static LinkedList<String> queue = new LinkedList<>();
    // 存储运算符
    static LinkedList<String> stack = new LinkedList<>();

    // 运算符正则
    public static final String REG_SYMBOL = "[+\\-*/%()]";
    // 数字正则
    public static final String REG_NUMERIC = "^(-?\\d+)(\\.\\d+)?$";

    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS = "-";
    static final String MULTIPLICATION = "*";
    static final String DIVISION = "/";
    static final String SURPLUS = "%";

    static final List<Character> opt = Arrays.asList('+', '-', '*', '/', '%', '(', ')');

    static {
        // 运算符优先级规则
        operators = new HashMap<>();
        operators.put("+", 2);
        operators.put("-", 2);
        operators.put("*", 4);
        operators.put("/", 4);
        operators.put("%", 4);
        operators.put("(", 128);
        operators.put(")", 128);
    }


    /**
     * 中缀表达式转后缀表达式
     *
     * @param express 中缀表达式
     * @return 后缀表达式
     */
    public static List<String> convertMid2Suffix(String express) {
        if (express == null || "".equals(express)) return null;
        String target = replaceAllBlank(express);
        // 2. 遍历中缀表达式
        int len = target.length();
        int i = 1, start = 0;
        for (; i < len; i++) {
            // 3. 如果是操作数，放入队列
            char e = target.charAt(i);
            if (isSymbol(e)) {
                // 数字存入队列
                if (start != i) {
                    String num = target.substring(start, i);
                    queue.add(num);
                }
                start = i + 1;
                if (stack.isEmpty() || '(' == e || "(".equals(stack.peek())) {
                    // 4. 如果是非操作数

                    // 5. 栈2为空或者是'(' 或者栈顶为’('直接存入栈
                    stack.push(e + "");
                } else if (')' == e) {
                    // 6. 当前元素为')’,出栈中元素放入队列，直至'('
                    String t;
                    while (!stack.isEmpty() && !"(".equals(t = stack.pop())) {
                        queue.add(t);
                    }
                } else {
                    // 7. 元素不为‘)'
                    // 8. 比较栈顶元素与当前元素优先级
                    while (!stack.isEmpty() && comparePriority(e + "", stack.peek())) {
                        // 9. 当前运算符优先级不大于栈顶运算符优先级，弹栈放入队列，
                        queue.add(stack.pop());
                    }
                    // 10. 当前元素优先级高直接放入栈中
                    stack.push(e + "");
                }

            } else if (isNumeric(e)) {

            } else {
                throw new RuntimeException("非法表达式");
            }

        }
        if (start != i) {
            String num = target.substring(start, i);
            queue.add(num);
        }
        // 10. 表达式遍历结束
        while (!stack.isEmpty()) {
            queue.add(stack.pop());
        }
        // 11. 队列元素转换为字符串即为后缀表达式
        return queue;
    }

    /**
     * 计算后缀表达式
     *
     * @param suffix
     * @return
     */
    public static double calSuffix(List<String> suffix) {
        LinkedList<Double> oprs = new LinkedList<>();
        for (String s : suffix) {
            if (isNumeric(s))
                oprs.push(Double.parseDouble(s));
            else {
                Double opr2 = oprs.pop();
                Double opr1 = oprs.pop();
                oprs.push(calc2(opr1, opr2, s));
            }
        }
        return oprs.pop();
    }

    private static Double calc2(Double opr1, Double opr2, String s) {
        double ret = 0;
        switch (s) {
            case "+":
                ret = opr1 + opr2;
                break;
            case "-":
                ret = opr1 - opr2;
                break;
            case "*":
                ret = opr1 * opr2;
                break;
            case "/":
                ret = opr1 / opr2;
                break;
            case "%":
                ret = opr1 % opr2;
                break;
            default:
                break;
        }
        return ret;
    }

    /**
     * 去除所有空白符
     *
     * @param s 目标字符串
     * @return 去除空白字符后字符串
     */
    public static String replaceAllBlank(String s) {
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+", "");
    }

    /**
     * 判断是否是数字
     *
     * @param s 目标字符串
     * @return true-是数字;false-不是数字
     */
    public static boolean isNumeric(String s) {
        return !operators.containsKey(s);
    }

    /**
     * 判断单个字符是否是数字
     *
     * @param s 目标字符
     * @return true-是数字;false-不是数字
     */
    public static boolean isNumeric(char s) {
        return (s >= 48 && s <= 57) || s == 46;
    }

    /**
     * 根据事先定义好的规则比较运算符的优先级
     *
     * @param o1 运算符1
     * @param o2 运算符2
     * @return 运算符1优先级是否不大于运算符2优先级?true:false
     */
    public static boolean comparePriority(String o1, String o2) {
        return operators.get(o1) - operators.get(o2) <= 0;
    }

    /**
     * 判断字符串是否是数字
     *
     * @param s 目标字符串
     * @return true-是数字;false-不是数字
     */
    public static boolean isNumericReg(String s) {
        return s.matches(REG_NUMERIC);
    }

    /**
     * 判断字符串是否是运算符
     *
     * @param s 目标字符串
     * @return true-是运算符;false-不是运算符
     */
    public static boolean isSymbolReg(String s) {
        return s.matches(REG_SYMBOL);
    }

    /**
     * 判断字符是否是运算符
     *
     * @param s 目标字符
     * @return true-是运算符;false-不是运算符
     */
    public static boolean isSymbol(char s) {
        return opt.contains(s);
    }
}
